This invention relates to three-dimensional (xe2x80x9c3Dxe2x80x9d) modeling of real-world objects, terrains and other surfaces by computer. In particular, the present invention relates to a system and method for smooth surface interpolation for arbitrary meshes.
Portions of the disclosure of this patent document contain material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
There is great interest in the development of computer systems which enable users to generate accurate displays and reproductions of real world and fantasy objects, terrains and other 3D surfaces. A graphic display and manipulation system generates a mesh model of the object, terrain or surface, uses that mesh model as a basis to create the display or reproduction. A mesh model represents an object, terrain or other surface as a series of interconnected planar shapes, such as triangles, quadrangles or more complex polygons. More advanced graphic display systems provide rapid zoom and xe2x80x9cwalk aroundxe2x80x9d capabilities (allowing the user to make his or her perceived vantage point appear to move closer to, farther from or about an object or surface).
A set of data points that describes the object or surface provides basic data for the mesh. The data points, in many cases, represent actual, measured points on the object, surface or terrain. Values for such measured data points may come from a number of sources. A user can input data points based on measurement or planned architecture or they can be generated through scanning and other measuring systems. A scanning system uses a light source such as a laser stripe to scan and a camera to collect images of the scanning light as it reflects from the object. A scanning system processes the information captured in the images to determine a set of measured 3D point values that describe the object, surface or terrain in question.
Typical mesh modeling systems use data points (such as measured data points) to create meshes of the object, surface or terrain. When modeling a complex object, the meshes often have sharp changes of surface contour in localized areas of detail. For example, when modeling a human face, the area of the mesh model for the nose or the eyes will usually have more changes of contour than the surface area of the cheek. In some circumstances the model designers will sometimes wish to heighten or further refine the contours in these areas to provide a model of the object which is more realistic in appearance or which has a special focus.
Traditional tools of 3D modeling include the use of Bezier splines, Non-Uniform Rational B-Splines (NURBS) and other types of patch based surface modeling. These tools are efficient for simple shapes such as boxes, spheres and cylinders, but quickly become awkward for constructing and providing a sufficient level of detail resolution for surfaces that are more irregularly shaped, such as organic shapes resulting from 3D scanning. As the terrain of a complex object changes rapidly, and in a random fashion, a global function calculation, such as a B-Spline, requires a significant portion of the computer""s resources and may not provide a model that has sufficient detail in the areas of interest. Thus, for mesh models of irregularly shaped surfaces, such as real-world or fantasy objects, surfaces or terrains, there is a need for the development of new computer tools for permitting refinement to such complex surfaces. In mathematical terms, one problem to be solved can be stated as follows: Given a base mesh, such as a triangulated surface, how can the mesh be refined to produce a smooth surface that passes through all of the initial vertices orthogonal to the initial normal vectors at each of the vertices.
Over the last decade, developers have made attempts to create algorithms for refining the detail of complex, irregular surfaces. One generally known approach, is the so-called xe2x80x9csubdivision of surfacesxe2x80x9d technique. As applied to the smoothing of 3D triangulated meshes, this technique seeks to recursively subdivide all of the triangles of the mesh into four-sub triangles, until the desired level of detail is reached. FIG. 1 shows an example of this subdivision of a single triangle 1 into a triangulated mesh having original vertices 11, 12, and 13. The edges 2, 3, 4 of triangle 1 are subdivided by adding new vertices 21, 22, and 23 at the midpoints of each edge 2, 3, 4 of triangle 1. These new vertices can be determined or extruded based on an extrusion algorithm and four new triangles 31, 32, 33 and 34 can be rendered. Each of these smaller triangles 31-34 may also be subdivided and extruded in a similar manner to further refine the mesh.
However, there are drawbacks to the subdivision of surfaces technique, including a likelihood of overwhelming a computer""s resources. In certain implementations, each global subdivision using this technique quadruples the used memory. For example, a mesh having 10,000 triangles would have 40,000 triangles after the first iteration of a subdivision. Such subdivision could quickly overwhelm the memory resources of the computer, causing it to be unable to render and animate such a surface after a small number of subdivisions. In addition, this type of recursive subdividing produces a uniform surface geometry when each triangle is always subdivided in the same manner. These subdivisions may not create a surface which passes through the orthogonals of the initial vertices in an efficient manner. Accordingly, there is a need for new techniques to subdivide a mesh model in a way which would provide greater accuracy and efficiency in terms of subdivisions which create a surface that best passes through all of the initial vertices orthogonal to the initial normals and which also uses the available computing resources in the most efficient manner. In the search for better mesh modeling systems, it is important to look at criteria such as:
how to avoid doing unnecessary subdivisions at smooth areas;
how to determine or extrude the middle points of the edges;
how to guarantee numerical stability and robustness; and
how to achieve real-time performance using commonly available computer equipment.
One goal is to prevent unnecessary subdivisions with a algorithm that is adaptive so that it permits the making of an efficient subdivision at any level of recursion. The second issue pertains to the mathematical accuracy of the subdivision. The extrusion technique should provide a certain smoothness of the surface in the limit of infinite subdivision. Additionally, normal vectors to this limiting surface have to interpolate those at the base mesh vertices, which requirement gives another restriction on the extrusion algorithm.
The third issue pertains to practical implementation. xe2x80x9cBadxe2x80x9d areas, such as high peaks may produce instabilities at each level of subdivision, which may go to infinity in the limit of infinite level. The last issue has to do with computational complexity. The algorithm should take linear time. Moreover, very few operations should be performed in every triangle, so that speeds of, for example 10 frames/sec, can be achieved by using available computer hardware, such as an Intel Pentium II(trademark) processor.
With problems such as these solved, adaptive subdivision may become a basic tool of 3D graphics, like Gourand shading. Hardware acceleration may lead to speeds of 30 frames/sec or more, after which a new level of realism in 3D graphics can be achieved. However, to date there are no tools which can produce a smooth mesh model with the desired efficiency, detail and accuracy.
The present invention provides a computer-based system and method for the adaptive subdivision of mesh model of a three-dimensional (3D) object or surface that results in a smooth interpolation of the mesh surface. The mesh model has a set of connected faces, with each face being a geometric shape with a predetermined number of vertices and a corresponding number of edges. Each edge connects two of the predetermined number of vertices. The system adds detail to the mesh model through the adaptive subdivision of the faces of the mesh model.
In the exemplary embodiment which operates upon a triangulated mesh model, the system of the present invention analyzes each edge of the triangle in question to determine whether that particular edge should be subdivided based on a predetermined subdivision criteria. After an analysis of each of the edges of that triangle (using the adaptive subdivision criteria) the system and method of the present invention makes one of several different types of subdivisionsxe2x80x94e.g. dividing the mesh triangle into two, three or four smaller triangles.
When analyzing each edge of the triangle, the system and method of the present invention will determine the 3D coordinates for a point which will subdivide that triangle edge and compute other information that would be related to that point, such as normal information (and other information such as attribute information like, color or shine (reflectivity) information). When a triangle""s edge is subdivided, each edge segment can also be further analyzed to determine whether it will need to be further subdivided. Once each edge is analyzed, and the subdivision points generated, the triangle can be subdivided and new triangles adding additional detail or refinement to the mesh.
In an exemplary embodiment, a subdivision element receives data concerning one of the triangles to be analyzed and then checks the first edge (by checking the data associated with the vertices for that edge) against a predetermined subdivision criteria. The subdivision criteria can analyze mesh edge and data point characteristics such as the length of the edge (subdividing the edge if the length greater than a predetermined threshold) or the angle between the normal vectors at the two edge vertices (subdividing the edge if the angle is greater than a predetermined threshold). However, the meshing system of the present invention can be arranged to analyze other attribute information associated with the mesh or its data points, such as color or shine (reflectivity) information and make subdivision determinations based on those criteria as well. When an edge meets the predetermined subdivision criteria, an extrusion element determines the coordinate and other mesh attribute information that is to be associated with the new subdivision point. In the exemplary embodiment, the coordinates are smoothly interpolated so that they will lie on a curve that passes through the vertices of the first edge orthogonal to the normal vectors at the first edge vertices. (Values for other attributes of the data point such as color would be interpolated based on the data associated with the original vertices in much the same manner).
If a determination is made to subdivide a triangle""s edge, the system and method of the present invention, will (e.g. in a recursive procedure) further analyze the subedges formed by the newly created data point and the original edge vertices to determine if further subdividing of those subedges is necessary. When analysis of an edge is completed, the system and method of the present invention continues to analyze the other edges in the original triangle to determine whether those edges require subdivision(s). After each edge of a triangle is analyzed, the system and method of the present invention will subdivide the triangle into further subtriangles, e.g making either a double (two triangle), triple (three triangle) or quadruple (four triangle) subdivision, depending upon the number of edges that were determined to need subdivision. The system then proceeds (e.g. in a recursive procedure) to analyze those newly created subtriangles to determine if further subdivisions are necessary within them.